package com.czk.algorithm.dijkstra;

import java.util.Arrays;

/**
 * @Author:ChenZhangKun
 * @Date: 2020/8/10 20:22
 */
public class Dijsktra {
    public static void main(String[] args) {
        char[] vertex={'A','B','C','D','E','F','G'};
        int[][] matrix=new int[vertex.length][vertex.length];
        // 用最大int常量表示不可连接
        final int INF=65535;
        matrix[0]=new int[]{INF,5,7,INF,INF,INF,2};
        matrix[1]=new int[]{5,INF,INF,9,INF,INF,3};
        matrix[2]=new int[]{7,INF,INF,INF,8,INF,INF};
        matrix[3]=new int[]{INF,9,INF,INF,INF,4,INF};
        matrix[4]=new int[]{INF,INF,8,INF,INF,5,4};
        matrix[5]=new int[]{INF,INF,INF,4,5,INF,6};
        matrix[6]=new int[]{2,3,INF,INF,4,6,INF};
        Graph graph=new Graph(vertex,matrix);
        graph.djs(6);
        graph.show();

       //graph.showGraph();
    }
}
class Graph{
    /**
     * 顶点数组
     */
    char[] vertex;
    /**
     * 邻接矩阵
     */
    int[][] matrix;
    VisitedVertex visitedVertex;
    public Graph() {
    }

    /**
     * 构造
     * @param vertex
     * @param matrix
     */
    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }
    public void showGraph(){
        for (int[] ints : this.matrix) {
            System.out.println(Arrays.toString(ints));
        }
    }

    /**
     * 迪杰斯特拉算法
     * @param index 开始索引
     */
    public void djs(int index){
         this.visitedVertex=new VisitedVertex(vertex.length,index);
         // 更新
        this.update(index);
        for (int i = 0; i < vertex.length; i++) {
            int i1 = visitedVertex.updateAddr();
            update(i1);
        }
    }

    /**
     * 更新index到周围顶点的距离和前驱结点
     * @param index
     */
    public void update(int index){
        int len;
        for (int i = 0; i < matrix[index].length; i++) {
            // 出发顶点到index的距离+index到i的距离
            len=visitedVertex.getDis(index)+this.matrix[index][i];
            // 如果i没有被访问过，并且len小于出发点到i的距离
            if (!visitedVertex.in(i)&&len<visitedVertex.getDis(i)){
                // 更新出发顶点到i的距离为len
                visitedVertex.updateDis(i,len);
                // 更新i的前驱节点为index
                visitedVertex.updatePre(i,index);
            }
        }
    }
    /**
     * 显示
     */
    public void show(){
        visitedVertex.show();
    }
}
class VisitedVertex{
    /**
     * 记录各个顶点是否被访问过
     * 1 被访问 0没被访问
     * 会动态更新
     */
    int[] already_arr;
    /**
     * 记录每个下标的值为前一个顶点的下标，会动态更新
     */
    int[] pre_vertex;
    /**
     * 记录出发顶点到其他顶点的距离
     */
    int[] dis;

    /**
     *
     * @param length 顶点的个数
     * @param index 出发顶点的索引
     */
    public VisitedVertex(int length,int index) {
        already_arr=new int[length];
        pre_vertex=new int[length];
        dis=new int[length];
        // 初始化dis距离数组,此时都设置为最大值
        Arrays.fill(dis,Integer.MAX_VALUE);
        // 设置出发顶点被访问过
        already_arr[index]=1;
        this.dis[index]=0;
    }

    /**
     * 判断索引为index的顶点是否被访问过
     * @param index 索引
     * @return
     */
    public boolean in(int index){
        return already_arr[index]==1;
    }

    /**
     * 更新距离
     * @param index 索引
     * @param len 长度
     */
    public void updateDis(int index,int len){
        dis[index]=len;
    }

    /***
     * 更新pre顶点的前驱顶点为index这个顶点
     * @param pre
     * @param index
     */
    public void updatePre(int pre,int index){
        pre_vertex[pre]=index;
    }

    /**
     * 得到出发顶点到index顶点的距离
     */
    public int getDis(int index){
        return dis[index];
    }

    /**
     * 继续选择并返回新的访问顶点，例如G->A后，此时A为新的顶点
     * @return
     */
    public int updateAddr(){
        int min=65535,index=0;
        for (int i = 0; i < already_arr.length; i++) {
            if (already_arr[i]==0&&dis[i]<min){
                min=dis[i];
                index=i;

            }
        }
        already_arr[index]=1;
        return index;
    }
    public void show(){
        for (int i : already_arr) {
            System.out.println(i);
        }
        System.out.println("==============");
        for (int preVertex : pre_vertex) {
            System.out.println(preVertex);
        }
        System.out.println("===============");
        for (int di : dis) {
            System.out.println(di);
        }
    }
}
